/*
 * @lc app=leetcode.cn id=402 lang=java
 *
 * [402] 移掉 K 位数字
 */

// @lc code=start

import java.util.Stack;

class Solution {
    public String removeKdigits(String num, int k) {
        if(num.length() == k) {
            return "0";
        }

        char[] s = num.toCharArray();
        Stack<Character> stack = new Stack<>();

        // 遍历数组
        for(Character c : s) {
            // 当栈不为空，k>0，且栈顶元素大于当前元素时，出栈
            while(!stack.isEmpty() && k > 0 && stack.peek() > c) {
                stack.pop();
                k--;
            }
            // 当栈为空时，且当前元素为0时，不入栈
            if(stack.isEmpty() && c == '0') {
                continue;
            }

            stack.push(c);

        }
        // 当k>0时，继续出栈
        while(!stack.isEmpty() && k > 0) {
            stack.pop();
            k--;
        }

        // 当栈为空时，返回0
        if(stack.isEmpty()) {
            return "0";
        }

        // 将栈中元素转为字符串
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()) {
            sb.append(stack.pop());
        }

        return sb.reverse().toString();
    }
}
// @lc code=end

